package binaryTree;

import java.time.temporal.ChronoUnit;
import java.util.*;

/**
 * @program: java_concurrent
 * @description: 传递节点集合以及二元关系集合，判断是否是树
 *
 * 根据树的结构定义， 加上树的一组基本操作就构成了树的抽象数据类型定义：
 * ADT Tree{
 * 数据对象D: D是具有相同特性的数据元素的集合。
 * 数据关系R: 若D为空集，则称为空树；
 * 若D仅含一个数据元素，则R为空集，否则R={H}, H是如下二元关系：
 * (1) 在D中存在唯一的称为根的数据元素root,-它在关系H下无前驱；
 * (2) 若D-{root} ≠ ∅，则存在D-{root}的一个划分 D1, D2, …，Dm(m>0), 对任意j ≠ k(1≤j, k≤m) 有
 * Dj∩Dk = ∅, 且对任意的 i(1≤i≤m), 唯一存在数据元素xi ∈ Di, 有<root,xi> ∈ H;
 * (3) 对应于D-{root}的划分，H-{ <root, x1>, …，<root,xm>} =有唯一的一个划分H1, H2, …,
 *  Hm (m> 0), 对任意j ≠ k(1≤j, k≤m)有Hj∩Hk =ct>, 且对任意ii(1≤i≤m), Hi是Di上的二元关
 * 系，(Di, {Hi}) 是一棵符合本定义的树，称为根root的子树。
 *
 *
 * @author: lxf
 * @create: 2024-05-30 11:13
 **/
public class JudgeTree {



    public boolean judge(List<String> nodes, List<String> relationships){
        // 空树,只包含根节点的树
        if (nodes.size() == 0 || nodes == null ||nodes.size() == 1) return true;

        Map<String,List<String>> map = handleRealtionshipsToMap(relationships);

        String root = findRoot(nodes,relationships);
        if (root == null) return false;

        List<List<String>> Di = groupDi(root,nodes,map);
        List<Map<String,List<String>>> Hi = groupHi(root,nodes,relationships,map);
        return false;
    }

    private List<List<String>> groupDi(String root, List<String> nodes,  Map<String,List<String>> map) {
        List<List<String>> Di = new ArrayList<>();
        // 获取子树根节点
        List<String> sonsOfRoot = map.get(root);
        for (String son : sonsOfRoot) {
            List<String> sonsOfNode = map.get(son);
        }
        return null;
    }

    private List<Map<String, List<String>>> groupHi(String root, List<String> nodes, List<String> relationships, Map<String, List<String>> map) {
        return null;
    }

    private Map<String, List<String>> handleRealtionshipsToMap(List<String> relationships) {
        Map<String, List<String>> map = new HashMap<>();
        for (String relationship : relationships) {
            String[] parts = relationship.split(","); // 假设逗号不会出现在其他位置
            String key = parts[0].trim(); // 去除可能的空格
            String value = parts[1].trim(); // 去除可能的空格
            // 如果键不存在于Map中，则添加一个新的空列表
            map.putIfAbsent(key, new ArrayList<>());
            // 将值添加到对应键的列表中，确保值是唯一的
            map.get(key).add(value);
        }
        return map;
    }



    private String findRoot(List<String> nodes, List<String> relationships) {
        List<String> secondNodes = new ArrayList<>();
        relationships.forEach(relationship -> {
            String[] split = relationship.split(",");
            secondNodes.add(split[1]);
        });
        // 创建一个nodes的副本，以免修改原始nodes列表
        List<String> root = new ArrayList<>(nodes);
        root.removeAll(secondNodes);
        if (root.isEmpty() || root.size()>1) return null;
        return root.get(0);
    }
}
